package leetcode.code0686;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	public int repeatedStringMatch(String a, String b) {
		char[] chars1 = a.toCharArray();
		char[] chars2 = b.toCharArray();
		int len1 = chars1.length;
		int len2 = chars2.length;
		int[] p = new int[len2];
		// p中m位置记录数值n,表示[0,n-1]的字符串同[m-n+1,m]字符串相同
		for (int i = 1, j = 0; i < len2 && j < len2; i++) {
			while (j > 0 && chars2[i] != chars2[j]) {
				j = p[j - 1];
			}
			if (chars2[i] == chars2[j]) {
				j++;
			}
			p[i] = j;
		}
		int i = 0;
		int tail = 0;
		for (int j = 0; j < len2; i++) {
			while (j > 0 && chars1[i % len1] != chars2[j]) {
				j = p[j - 1];
			}
			if (chars1[i % len1] == chars2[j]) {
				j++;
			}
			if (i == len1 - 1) {
				tail = j + 1;
				if (tail == 0) {
					return -1;
				}
			}
			if (i / len1 > 1 && (i / len1 - 1) * len1 + tail + i % len1 != j) {
				return -1;
			}
		}
		int ans = i % len1 == 0 ? i / len1 : i / len1 + 1;
		return ans;//
	}

	@Override
	public void debug1() {
		HelpDebug.compare(3, this.repeatedStringMatch("abcd", "cdabcdab"));
	}

	@Override
	public void debug2() {
		HelpDebug.compare(-1, this.repeatedStringMatch("abcd", "xzy"));
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub
		HelpDebug.compare(-1, this.repeatedStringMatch("abaabaa", "abaababaab"));
	}

	@Override
	public void debug4() {
		//
		HelpDebug.compare(-1, this.repeatedStringMatch("abcd", "cdabcdacdabcda"));
	}

	public void debug5() {
		// ""
		HelpDebug.compare(2, this.repeatedStringMatch("aabaa", "aaab"));
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug5();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
